package com.jyl.sort.merge;

import java.util.Arrays;

/**
 * 理解归并 --> 将两个有序数组归并成一个有序数组
 *
 * @ClassName Merge
 * @Author admin
 * @Date 2024/6/14
 */
public class Merge {

    public static void main(String[] args) {
        int[] arr1 = {1, 3, 5, 7, 9, 11, 13};
        int[] arr2 = {2, 4, 6, 8, 10, 12};

        int[] mergeArray = merge(arr1, arr2);
        System.out.println(Arrays.toString(mergeArray));

        // 测试merge(int[] nums,int start.....)
        int[] arr3 = {1, 3, 5, 7, 9, 11, 13,2, 4, 6, 8, 10, 12};
        merge(arr3,0,6,12);
        System.out.println("info: "+Arrays.toString(arr3));

    }

    /**
     * 目的: 将两个有序数组合并为一个有序数组
     * 步骤: 遍历两个有序数组,比较数组中对应的元素,把最小的元素放入零时数组中
     */
    protected static int[] merge(int[] arr1, int[] arr2) {
        int[] tempArray = new int[arr1.length + arr2.length];

        int firstPointer = 0;
        int endPointer = 0;
        int tPointer = 0;


        // 比较有序数组中的元素
        while (firstPointer < arr1.length && endPointer < arr2.length) {
            tempArray[tPointer++] = arr1[firstPointer] < arr2[endPointer] ? arr1[firstPointer++] : arr2[endPointer++];
        }

        // 当上面循环结束，通过判断指针是否等于数组的长度，就能分辨出具体是哪个数组中的元素比较完了 (最后一次循环，index++后正好等于length)
        while (firstPointer < arr1.length) {
            tempArray[tPointer++] = arr1[firstPointer++];
        }

        while (endPointer < arr2.length) {
            tempArray[tPointer++] = arr2[endPointer++];
        }

        return tempArray;
    }

    /**
     * 需求：将
     *         arr1[start--mid] ,
     *         arr2[mid+1--end]
     *  合并到 nums[start--end]
     */
    protected static void merge(int[] nums, int start, int mid, int end) {
        int[] result = new int[end - start + 1];

        int arrOnePointer = start;
        int arrTwoPointer = mid + 1;
        int resultPointer = 0;

        // arrOnePointer 和 arrTwoPointer 的最大取值均能取到 mid 和 end 所以得 <=
        while (arrOnePointer <= mid && arrTwoPointer <= end) {
            result[resultPointer++] = nums[arrOnePointer] < nums[arrTwoPointer] ? nums[arrOnePointer++] : nums[arrTwoPointer++];
        }

        while (arrOnePointer <= mid) {
            result[resultPointer++] = nums[arrOnePointer++];
        }

        while (arrTwoPointer <= end) {
            result[resultPointer++] = nums[arrTwoPointer++];
        }

        //将临时数组的内容拷贝到原数组指定区间
        System.arraycopy(result,0,nums,start,result.length);
    }


}
